package Leetcode.搜索与回溯;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: kirito
 * @Date: 2024/4/22 0:02
 * @Description:
 * 组合总和 Ⅳ
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
 *
 * 题目数据保证答案符合 32 位整数范围。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3], target = 4
 * 输出：7
 * 解释：
 * 所有可能的组合为：
 * (1, 1, 1, 1)
 * (1, 1, 2)
 * (1, 2, 1)
 * (1, 3)
 * (2, 1, 1)
 * (2, 2)
 * (3, 1)
 * 请注意，顺序不同的序列被视作不同的组合。
 * 示例 2：
 *
 * 输入：nums = [9], target = 3
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 1000
 * nums 中的所有元素 互不相同
 * 1 <= target <= 1000
 */

public class combinationSum4 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int target = 4;
        System.out.println(new combinationSum4().combinationSum4_1(arr, target));
    }

    /**
     * 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
     *
     * 顺序不同的序列被视作不同的组合
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1); // -1 表示没有计算过
        return dfs(target, nums, memo);
    }

    /**
     *
     * res
     * @param i i代表还需要爬多少层楼梯
     * @param nums  原数组
     * @param memo  记忆，memo[i] 代表爬i层需要多少次  不为-1的情况
     * @return
     */
    private int dfs(int i, int[] nums, int[] memo) {
        if (i == 0) { // 爬完了
            return 1;
        }
        if (memo[i] != -1) { // 之前计算过
            return memo[i];
        }
        int res = 0;
        for (int x : nums) { // 枚举所有可以爬的台阶数
            if (x <= i) {
                res += dfs(i - x, nums, memo);
            }else{
                break;
            }
        }
        //数组赋值，同时会把res返回，这个写法很怪味，没这些过
        return memo[i] = res; // 记忆化
    }

    /**
     * 动态规划
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4_1(int[] nums, int target) {
        Arrays.sort(nums);
        int[] dp = new int[target + 1];
        //dp[i] 表示选取的元素之和等于i的方案数
        //什么都不选 和就是0
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }else {
                    break;
                }
            }
        }
        return dp[target];
    }

}
